Quantum search algorithms are global random searching algorithms based on the principles, laws and effects of quantum mechanics. They are used for controlling a process or for processing data in a database, and more specifically, for controlling a process that may include search-of-minima intelligent operations.
In a quantum search, each design variable is represented by a finite linear superposition of initial states, with a sequence of elementary unitary steps manipulating the initial quantum state (for the input) such that a measurement of the final state of the system yields the correct output. Usually, three principle operators, i.e., linear superposition (coherent states), entanglement and interference are used in the quantum search algorithm.
For a better understanding, a brief description of quantum search algorithms is provided. The problems solved by quantum algorithms may be stated as follows:
InputA function f: {0, 1}n → {0, 1}mProblemFind a certain property of fThe structure of a quantum algorithm is outlined by a high level representation in the schematic diagram of FIG. 1.
The input of a quantum algorithm is a function f from binary strings into binary strings. This function is represented as a map table, which defines for every string its image. Function f is first encoded into a unitary matrix operator UF depending on f properties. This operator calculates f when its input and output strings are encoded into canonical basis vectors of a Complex Hilbert Space: UF maps the vector code of every string into the vector code of its image by f.
                                                              ⁢                      BOX            ⁢                                                  ⁢            1            ⁢                          :                        ⁢                                                  ⁢            UNITARY            ⁢                                                  ⁢            MATRIX            ⁢                                                  ⁢                          U              F                                                                    A          ⁢                                          ⁢          squared          ⁢                                          ⁢          matrix          ⁢                                          ⁢                      U            F                    ⁢                                          ⁢          on          ⁢                                          ⁢          the          ⁢                                          ⁢          complex          ⁢                                          ⁢          field          ⁢                                          ⁢          is          ⁢                                          ⁢          unitary                                              if          ⁢                                          ⁢          its          ⁢                                          ⁢          inverse          ⁢                                          ⁢          matrix          ⁢                                          ⁢          coincides          ⁢                                          ⁢          with          ⁢                                          ⁢          its          ⁢                                          ⁢          conjugate                                              transposition          ⁢                      :                                                                                        ⁢                                    U              F                              -                1                                      =                          U              F                                                                    A          ⁢                                          ⁢          unitary          ⁢                                          ⁢          matrix          ⁢                                          ⁢          is          ⁢                                          ⁢          always          ⁢                                          ⁢          reversible          ⁢                                          ⁢          and          ⁢                                          ⁢          preserves                                              the          ⁢                                          ⁢          norm          ⁢                                          ⁢          of          ⁢                                          ⁢                      vectors            .                                 
When the matrix operator UF has been generated, it is embedded into a quantum gate G, a unitary matrix whose structure depends on the form of matrix UF and on the problem to be solved. The quantum gate is the core of a quantum algorithm. In every quantum algorithm, the quantum gate acts on an initial canonical basis vector (the same vector may always be chosen) to generate a complex linear combination (called a superposition) of basis vectors as the output. This superposition contains all the information to answer the initial problem.
After this superposition has been created, a measurement takes place to extract this information. In quantum mechanics, measurement is a non-deterministic operation that produces as output only one of the basis vectors. The probability of every basis vector being the output of a measurement depends on its complex coefficient (probability amplitude) in entering a complex linear combination.
The segmental action of the quantum gate and of the measurement forms the quantum block. The quantum block is repeated k times to produce a collection of k basis vectors. In measuring a non-deterministic operation, these basis vectors would not be necessarily identical and each one of them will encode a piece of the information needed to solve the problem.
The last part of the algorithm includes interpretation of the collected basis vectors to get the right answer for the initial problem with a certain probability.
The behavior of the encoder block is described in the detailed schematic diagram of FIG. 2. Function f is encoded into matrix UF in three steps.
Step 1: The map table of function f: {0,1}n→{0,1}m is transformed into the map table of the infective function F: {0,1}n+m→{0,1}n+m such that:F(x0, . . . , xn−1, y0, . . . , ym−1)=(x0, . . . , xn−1, f(x0, . . . , xn−1)⊕(y0, . . . , ym−1))  (1)
                              BOX          ⁢                                          ⁢          2          ⁢                      :                    ⁢                                          ⁢          XOR          ⁢                                          ⁢          OPERATOR                ⁢                                  ⊕                                The        ⁢                                  ⁢        XOR        ⁢                                  ⁢        operator        ⁢                                  ⁢        between        ⁢                                  ⁢        two        ⁢                                  ⁢        binary        ⁢                                  ⁢        strings        ⁢                                  ⁢        p        ⁢                                  ⁢        and        ⁢                                  ⁢        q                                          of          ⁢                                          ⁢          length          ⁢                                          ⁢          m          ⁢                                          ⁢          is          ⁢                                          ⁢          a          ⁢                                          ⁢          string          ⁢                                          ⁢          s          ⁢                                          ⁢          of          ⁢                                          ⁢          length          ⁢                                          ⁢          m          ⁢                                          ⁢          such          ⁢                                          ⁢          that          ⁢                                          ⁢          the                ⁢                                                                    i          ⁢                      -                    ⁢          th          ⁢                                          ⁢          digit          ⁢                                          ⁢          of          ⁢                                          ⁢          s          ⁢                                          ⁢          is          ⁢                                          ⁢          calculated          ⁢                                          ⁢          as          ⁢                                          ⁢          the          ⁢                                          ⁢          exclusive          ⁢                                          ⁢          OR                ⁢                                                                    between          ⁢                                          ⁢          the          ⁢                                          ⁢          i          ⁢                      -                    ⁢          th          ⁢                                          ⁢          digits          ⁢                                          ⁢          of          ⁢                                          ⁢          p          ⁢                                          ⁢          and          ⁢                                          ⁢          q          ⁢                      :                          ⁢                                                                                    ⁢                  p          =                      (                                          p                0                            ,              …              ⁢                                                          ,                              p                                  n                  -                  1                                                      )                                                                            ⁢                  q          =                      (                                          q                0                            ,              …              ⁢                                                          ,                              q                                  n                  -                  1                                                      )                                                            s          =                                    p              ⊕              q                        =                          (                                                                    (                                                                  p                        0                                            +                                              q                        0                                                              )                                    ⁢                                                                          ⁢                  mod                  ⁢                                                                          ⁢                  2                                ,                …                ⁢                                                                  ,                                                      (                                                                  p                                                  n                          -                          1                                                                    +                                              q                                                  n                          -                          1                                                                                      )                                    ⁢                                                                          ⁢                  mod                  ⁢                                                                          ⁢                  2                                            )                                      )            
The need to deal with an injective function comes from the requirement that UF is unitary. A unitary operator is reversible, so it cannot map two different inputs in the same output. Given that UF is the matrix representation of F, F is supposed to be infective. If the matrix representation of function f is directly used, a non-unitary matrix could be obtained since f could be non-injective. So, injectivity is fulfilled by increasing the number of bits and considering function F instead of function f. Function f can always be calculated from F by putting (y0, . . . , ym−1)=(0, . . . , 0) in the input string and reading the last m values of the output string.
Step 2: Function F map table is transformed into a UF map table, based upon the following constraint:∀s∈{0,1}n+m: UF[τ(s)]=τ[F(s)]  (2)The code map τ:{0,1}n+m→C2n+m (C2n+m is the target Complex Hilbert Space) is such that:
                                                                                          τ                  ⁡                                      (                    0                    )                                                  =                                                      (                                                                                            1                                                                                                                      0                                                                                      )                                    =                                                                                                            0                        〉                                            ⁢                                                                                          ⁢                                              τ                        ⁡                                                  (                          1                          )                                                                                      =                                                                  (                                                                                                            0                                                                                                                                          1                                                                                                      )                                            =                                                                      1                        〉                                                                                                                                                                                      τ                  ⁡                                      (                                                                  x                        0                                            ,                      …                      ⁢                                                                                          ,                                              x                                                  n                          +                          m                          -                          1                                                                                      )                                                  =                                                                            τ                      ⁡                                              (                                                  x                          0                                                )                                                              ⊗                                                                                  ⁢                    …                    ⁢                                                                                  ⊗                                          τ                      ⁡                                              (                                                  x                                                      n                            +                            m                            -                            1                                                                          )                                                                              =                                                                                                        x                        0                                            ⁢                      …                      ⁢                                                                                          ⁢                                              x                                                  n                          +                          m                          -                          1                                                                                      〉                                                                                                                   (        3        )                                                           ⁢                  BOX          ⁢                                          ⁢          3          ⁢                      :                    ⁢                                          ⁢          VECTOR          ⁢                                          ⁢          TENSOR          ⁢                                          ⁢                      PRODUCT            ⁢                                                  ⊗                                                  The        ⁢                                  ⁢        tensor        ⁢                                  ⁢        product        ⁢                                  ⁢        between        ⁢                                  ⁢        two        ⁢                                  ⁢        vectors        ⁢                                  ⁢        of        ⁢                                  ⁢        dimensions                                          h          ⁢                                          ⁢          and          ⁢                                          ⁢          k          ⁢                                          ⁢          is          ⁢                                          ⁢          a          ⁢                                          ⁢          tensor          ⁢                                          ⁢          product          ⁢                                          ⁢          of          ⁢                                          ⁢          dimension          ⁢                                          ⁢                      h            ·            k                          ,        such                                that        ⁢                  :                                                                                                                                x                  〉                                ⊗                                                    ⁢            y                    〉                =                                            (                                                                                          x                      1                                                                                                            …                                                                                                              x                      h                                                                                  )                        ⊗                          (                                                                                          y                      1                                                                                                            …                                                                                                              y                      k                                                                                  )                                =                                    (                                                                                                                  x                        1                                            ⁢                                              y                        1                                                                                                                                  …                                                                                                                                      x                        1                                            ⁢                                              y                        k                                                                                                                                  …                                                                                                                                      x                        h                                            ⁢                                              y                        1                                                                                                                                  …                                                                                                                                      x                        h                                            ⁢                                              y                        k                                                                                                        )                        ⇒                                                                                                      Physical                      ⁢                                                                                          ⁢                      interpretation                      ⁢                                              :                                                              _                                                                                                                    If  a  component of  a  complexvector  is  interpreted  as  theprobability  amplitude  of  a system  in  a  given  state  (indexedby  the  component  number),  thetensor  product  between  twovectors  describes  the  jointprobability  amplitude  of  twosystems  in  a  joint  state.                                                                                          